package a00_LeetCode.LinkedList;

import com.sun.jmx.snmp.SnmpNull;

/**
 * @Author quan
 * @Description 删除链表的倒数第 N 个结点：自己没写出来！！
 * @Date 2023/4/1 16:26
 */
public class Num19_removeNthFromEnd {
    /**
     * 答案：虚拟头结点+双指针
     * 双指针的经典应用，如果要删除倒数第n个节点，让fast移动n+1步，然后让fast和slow同时移动，直到fast指向链表末尾，此时slow指向被删除节点的前驱。
     * 删掉slow所指向的节点就可以了。
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode fast = dummyHead;
        ListNode low = dummyHead;
        for (int i = 0; i < n+1; i++) {
            fast = fast.next;
        }
        while (fast!=null){
            fast = fast.next;
            low = low.next;
        }
        low.next = low.next.next;
        return dummyHead.next;
    }
}
